package cn.edu.whu.lmars.dblgtree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Envelope;
import com.vividsolutions.jts.geom.LineSegment;
import com.vividsolutions.jts.geom.LineString;

/**
 * @author Xinlin Qian
 *
 */

//there are three types of nodes in DBLG-tree
	//1. 
public class LTreeNode {
	//four members associate to a LatestDBLGTree's node
	//the space requirement of a node is 4 * 4 + 4 * 4 + 2 * 8 + 4 = 52 bytes.
	private int rank = 0;

	//relative sequence number for latest dblg-tree
	private int nrank = 0;

	//error for the stable dblg-tree
	private float err = 0;

	//error for the latest tree
	private float nerr = 0;

	//the  number of update
	private int updates = 0;

	//coordinate of the vertex.
	//convert from double. the error of the rounding may less than a centimeter.
	private int x = 0;
	private int y = 0;

	//the updated coordinate of a node
	private int nx = 0;
	private int ny = 0;

	//indicate whether the node is a root of a invalid subtree 
	private boolean isInvalid = false;

	//two children to form a binary tree structure.
	private LTreeNode left = null;
	private LTreeNode right = null;

	//call this to construct an latest DBLG-tree of the specific polyline geometry object
	//LineString ln can be either closed or open.
	public static LTreeNode Init(LineString ln) {
		Coordinate[] coords = ln.getCoordinates();

		LTreeNode ltrt = simplify(coords, 0, coords.length - 1);

		//the real root node other than the two endpoint
		LTreeNode midnd = ltrt.duplicate();
		midnd.left = ltrt.left;
		midnd.right = ltrt.right;

		//attach the two endpoints to the tree
		LTreeNode evtx = new LTreeNode();
		evtx.setValues(coords.length - 1, coords.length - 1, Float.MAX_VALUE,
				Float.MAX_VALUE, (int) (coords[coords.length - 1].x * 1000000),
				(int) (coords[coords.length - 1].y * 1000000),
				(int) (coords[coords.length - 1].x * 1000000),
				(int) (coords[coords.length - 1].y * 1000000));
		evtx.left = midnd;

		ltrt.setValues(0, 0, Float.MAX_VALUE, Float.MAX_VALUE,
				(int) (coords[0].x * 1000000), (int) (coords[0].y * 1000000),
				(int) (coords[0].x * 1000000), (int) (coords[0].y * 1000000));
		ltrt.right = evtx;
		ltrt.left = null;

		//return the root of the DBLG-tree which corresponds with the inputed linestring
		return ltrt;
	}

	public static LTreeNode Init(LineString ln, ArrayList<Integer> commons) {
		Coordinate[] coords = ln.getCoordinates();
		commons.add(0, -1);
		commons.add(commons.size() - 1, -1);
		return simplifyC(coords, 0, coords.length - 1, 0, commons.size() - 1, commons);
	}

	//simplify with constraints
	private static LTreeNode simplifyC(Coordinate[] coords, int i, int j,
			int a, int b, ArrayList<Integer> commons) {

		if (a + 1 == b || a == b) {
			return simplify(coords, i, j);
		} else {
			int c = (a + b) / 2;
			LTreeNode lt = new LTreeNode();
			int pivot = commons.get(c);
			lt.setValues(pivot - i, pivot - i,
					Float.MAX_VALUE, Float.MAX_VALUE, 
					(int) (coords[pivot].x * 1000000),
					(int) (coords[pivot].y * 1000000),
					(int) (coords[pivot].x * 1000000),
					(int) (coords[pivot].y * 1000000));
			
			lt.left = simplifyC(coords, i, pivot, a, c, commons);
			lt.right = simplifyC(coords, pivot, j, c, b, commons);

    		return lt;
		}
	}

	private void setValues(int ra, int nra, float er, float ner, int x, int y,
			int nx, int ny) {
		this.rank = ra;
		this.nrank = nra;
		this.err = er;
		this.nerr = ner;
		this.x = x;
		this.y = y;
		this.nx = nx;
		this.ny = ny;
	}

	//windowing queries is the only query type the latest dblgtree need to handle.
	// inputs:
	//w : windowing query condition; every vertex falling in w should be returned.
	//mbr : a temporary object.
	//x1, y1, x2, y2 : the two point coordinates of simplified segment of current nodes
	// outputs:
	// subtree which represents the subline including all vertices falling in w.
	public LTreeNode wquery(Envelope w, Envelope mbr, int x1, int y1, int x2,
			int y2, int si, int se) {

		mbr.init(((double) x1) / 1000000, ((double) x2) / 1000000,
				((double) y1) / 1000000, ((double) y2) / 1000000);
		mbr.expandBy(nerr);

		if (w.contains(mbr)) {
			return fetchAll(si, se);
		} else if (!w.intersects(mbr)) {
			return null;
		}

		LTreeNode nd = duplicate();
		if (nrank > 1) {
			nd.left = left.wquery(w, mbr, x1, y1, x, y, si, si + nrank);
		}

		if (se - (si + nrank) > 1) {
			nd.right = right.wquery(w, mbr, x, y, x2, y2, si + nrank, se);
		}

		return nd;
	}

	public int getSize() {
		return right.nrank;
	}

	//get the most significant n vertices from the DBLG-tree using a priority breadth first traversal
	public LTreeNode iquery(int i, int si, int se) {
		PriorityQueue<Fullnode> pq = new PriorityQueue<Fullnode>(i,
				new FullnodeComp());

		LTreeNode duprt = duplicate();
		duprt.left = left;
		duprt.right = right;
		duprt.rank *= -1;

		Fullnode fn = new Fullnode();
		fn.node = duprt;
		fn.si = 0;
		fn.se = right.rank;

		pq.add(fn);

		int c = 0;
		while (c < i) {
			if (pq.size() < 1)
				break;
			Fullnode cnd = pq.poll();
			if (cnd.node.rank < 0) {
				cnd.node.rank *= -1;
			}

			if (cnd.node.rank > 1) {
				LTreeNode lnd = cnd.node.left.duplicate();
				lnd.left = cnd.node.left.left;
				lnd.right = cnd.node.left.right;
				lnd.rank *= -1;
				lnd.err = Math.min(cnd.node.err, lnd.err);
				cnd.node.left = lnd;

				Fullnode lfn = new Fullnode();
				lfn.si = cnd.si;
				lfn.se = cnd.si + cnd.node.rank;
				lfn.node = lnd;
				pq.add(lfn);
			} else {
				cnd.node.left = null;
			}

			if (cnd.se - (cnd.si + cnd.node.rank) > 1) {
				LTreeNode rnd = cnd.node.right.duplicate();
				rnd.left = cnd.node.right.left;
				rnd.right = cnd.node.right.right;
				rnd.rank *= -1;
				rnd.err = Math.min(cnd.node.err, rnd.err);
				cnd.node.right = rnd;

				Fullnode rfn = new Fullnode();
				rfn.si = cnd.si + cnd.node.rank;
				rfn.se = cnd.se;
				rfn.node = rnd;
				pq.add(rfn);
			} else {
				cnd.node.right = null;
			}

			c++;
		}

		//pq need to be cleaned
		pq.clear();

		//cut off the 'grey nodes'
		fn.node.cutOff();

		return fn.node;
	}

	public LTreeNode equery(double e, int si, int se) {

		if (err > e) {
			LTreeNode retnd = duplicate();
			if (rank > 1) {
				retnd.left = left.equery(e, si, si + rank);
			}

			if (se - (si + rank) > 1) {
				retnd.right = right.equery(e, si + rank, se);
			}

			return retnd;
		} else {
			return null;
		}
	}

	public LTreeNode viquery(Envelope w, int i, Envelope mbr) {

		PriorityQueue<Fullnode> pq = new PriorityQueue<Fullnode>(i,
				new FullnodeComp());

		LTreeNode lnd = duplicate();
		lnd.left = left;
		lnd.right = right;
		lnd.rank *= -1;

		Fullnode fnd = new Fullnode();
		fnd.node = lnd;
		fnd.si = 0;
		fnd.se = right.rank;

		pq.add(fnd);

		int c = 0;
		while (c < i) {

			if (pq.size() < 1) {
				break;
			}
			Fullnode tfd = pq.poll();

			//check the spatial condition
			mbr.init(((double) tfd.x1) / 1000000, ((double) tfd.x2) / 1000000,
					((double) tfd.y1) / 1000000, ((double) tfd.y2) / 1000000);
			mbr.expandBy(tfd.node.nerr);

			//
			if (w.intersects(mbr)) {

				if (tfd.node.rank < 0) {
					tfd.node.rank *= -1;
				}
				if (tfd.node.rank > 1) {
					LTreeNode ltd = tfd.node.left.duplicate();
					ltd.rank *= -1;
					ltd.left = tfd.node.left.left;
					ltd.right = tfd.node.left.right;
					ltd.nerr = ltd.err;
					ltd.err = Math.min(tfd.node.err, ltd.err);
					tfd.node.left = ltd;

					Fullnode lfd = new Fullnode();
					lfd.si = tfd.si;
					lfd.se = tfd.si + tfd.node.rank;
					lfd.setEndpoints(tfd.x1, tfd.y1, tfd.node.x, tfd.node.y);
					lfd.node = ltd;

					pq.add(lfd);
				}

				if (tfd.se - (tfd.si + tfd.node.rank) > 1) {
					LTreeNode rtd = tfd.node.right.duplicate();
					rtd.rank *= -1;
					rtd.left = tfd.node.right.left;
					rtd.right = tfd.node.right.right;
					rtd.nerr = rtd.err;
					rtd.err = Math.min(tfd.node.err, rtd.err);
					tfd.node.right = rtd;

					Fullnode rfd = new Fullnode();
					rfd.si = tfd.si + tfd.node.rank;
					rfd.se = tfd.se;
					rfd.setEndpoints(tfd.node.x, tfd.node.y, tfd.x2, tfd.y2);
					rfd.node = rtd;

					pq.add(rfd);
				}
				c++;
			}
		}

		pq.clear();

		fnd.node.cutOff();

		return fnd.node;
	}

	public LTreeNode vequery(Envelope w, double e, Envelope mbr, int x1,
			int y1, int x2, int y2, int si, int se) {

		mbr.init(((double) x1) / 1000000, ((double) x2) / 1000000,
				((double) y1) / 1000000, ((double) y2) / 1000000);
		mbr.expandBy(err);

		if (!w.intersects(mbr) || err <= e) {
			return null;
		}

		LTreeNode nd = duplicate();

		if (rank > 1) {
			nd.left = left.vequery(w, e, mbr, x1, y1, x, y, si, si + rank);
		}

		if (se - (si + rank) > 1) {
			nd.right = right.vequery(w, e, mbr, x, y, x2, y2, si + rank, se);
		}

		return nd;
	}

	public boolean insert(int pos, int x0, int y0, double arc) {
		int len = right.nrank;
		int slen = right.rank;
		
		if (pos < 0 || pos > right.nrank) {
			return false;
		}

		//right.left.getLatestSize(0, right.nrank);
		boolean isNeedRebuild = right.left.insert(pos, x0, y0, 0, 0, 0, 0, 0, -1,
				isInvalid, arc);

		len = right.nrank;

		//right.left.getLatestSize(0, right.nrank);
		if (isNeedRebuild) {
			//getLatestSize(0, -1);
			int[] diff = new int[1];
			int[] updatediff = new int[1];
			rebuild(pos, 0, 0, 0, 0, 0, len, 0, slen, diff, updatediff);

			//getLatestSize(0, -1);
		}
		return isNeedRebuild;
	}

	//inert a specific node from the latest dblgtree.
	//inputs:
	//pos: identifier of the vertex which is immediate predecessor of the inserting vertex.
	//nx, ny : coordinate of the newly inserted vertex.
	//si, se : the sequence number of current node's corresponding end points.
	//outputs:
	// whether the update incur a rebuilding
	private boolean insert(int pos, int x0, int y0, int x1, int y1, int x2,
			int y2, int si, int se, boolean isCovered, double arc) {

		//distance to the old line segment
		double plDis = new LineSegment(((double) x1) / 1000000,
				((double) y1) / 1000000, ((double) x2) / 1000000,
				((double) y2) / 1000000).distance(new Coordinate(
				((double) x0) / 1000000, ((double) y0) / 1000000));

		boolean retval = false;
		updates++;

		//updating the spatial information
		if (!isCovered) {

			if (!isInvalid && plDis <= err) {

			} else {
				if (plDis > err && plDis > nerr) {
					nerr = (float) plDis;
				}

				isInvalid = true;
				isCovered = true;
				if ((double) (se - si - 1) / updates < arc) {
					retval = true;
				}
			}

		} else {
			if (plDis > err && plDis > nerr) {
				nerr = (float) plDis;
			}
		}

		//
		if (se == pos && si + nrank == pos - 1) {
			if (right != null) {
				//throw exception here 

				//here need to revoke the deletion
				right.nrank = 1;
				right.nx = x0;
				right.ny = y0;
				right.nerr = (float) plDis;
				right.isInvalid = true;
				if (!isCovered) {
					right.updates = 1;
					retval = true;
				}

			} else {
				right = new LTreeNode();
				right.rank = 1;
				right.nrank = 1;
				right.err = -1;
				right.nerr = (float) plDis;
				right.x = x0;
				right.nx = x0;
				right.y = y0;
				right.ny = y0;
				right.isInvalid = true;
				right.updates = 1;
				if (!isCovered)
					retval = true;
			}
		} else if (si == pos - 1 && si + nrank == pos) {
			if (left != null) {
				//throw exception
				//System.out.println("error!");

				//here need to revoke the previous deletion
				left.nrank = 1;
				left.nx = x0;
				left.ny = y0;
				left.nerr = (float) plDis;
				left.updates = 1;
				left.isInvalid = true;
				if (!isCovered) {
					retval = true;
				}
				nrank++;

			} else {
				left = new LTreeNode();
				left.rank = 1;
				left.nrank = 1;
				left.err = -1;
				left.nerr = (float) plDis;
				left.x = x0;
				left.nx = x0;
				left.y = y0;
				left.ny = y0;
				left.isInvalid = true;
				left.updates = 1;
				if (!isCovered)
					retval = true;
				nrank++;
			}
		} else if (si + nrank >= pos) {
			boolean ret = left.insert(pos, x0, y0, x1, y1, x, y, si,
					si + nrank, isCovered, arc);
			retval = ret || retval;

			nrank++;

			// balance the tree
			if (err < 0) {
				maintain(false, si, se + 1, x1, y1, x2, y2);
			}

		} else {
			boolean ret = right.insert(pos, x0, y0, x, y, x2, y2, si + nrank,
					se, isCovered, arc);
			retval = ret || retval;
			//balance the tree using Size balance technique
			if (err < 0) {
				maintain(true, si, se + 1, x1, y1, x2, y2);
			}
		}

		return retval;
	}

	//balance the binary tree
	//using qifeng Cheng's method of size balanced binary tree
	private void maintain(boolean flag, int si, int se, int x1, int y1, int x2,
			int y2) {

		if (flag) {
			int rlsize = 0;
			if (right != null && right.left != null) {
				rlsize = right.nrank - 1;
			}

			int rrsize = 0;
			if (right != null && right.right != null) {
				rrsize = se - (si + nrank + right.nrank) - 1;
			}

			int lsize = 0;
			if (left != null) {
				lsize = nrank - 1;
			}

			if (rrsize > lsize) {
				lrotate(x1, y1, x2, y2);
			} else if (rlsize > lsize) {
				right.rrotate(nx, ny, x2, y2);
				lrotate(x1, y1, x2, y2);
			} else {
				return;
			}
		} else {
			// the size of left child of left child
			int llsize = 0;
			if (left != null && left.left != null) {
				llsize = left.nrank - 1;
			}

			int lrsize = 0;
			if (left != null && left.right != null) {
				lrsize = nrank - left.nrank - 1;
			}

			int rsize = 0;
			if (right != null) {
				rsize = se - (si + nrank) - 1;
			}
			if (llsize > rsize) {
				rrotate(x1, y1, x2, y2);
			} else if (lrsize > rsize) {
				left.lrotate(x1, y1, nx, ny);
				rrotate(x1, y1, x2, y2);
			} else {
				return;
			}
		}

		// this statement is in doubt of how to assign the si and se
		left.maintain(false, si, si + nrank, x1, y1, nx, ny);

		right.maintain(true, si + nrank, se, nx, ny, x2, y2);

		maintain(false, si, se, x1, y1, x2, y2);

		maintain(true, si, se, x1, y1, x2, y2);
	}

	private void rrotate(int x1, int y1, int x2, int y2) {

		// the pre-order traversal is : yxabc
		// the in-order traversal is : axbyc

		LTreeNode a = left.left;
		LTreeNode b = left.right;
		LTreeNode c = right;

		LTreeNode xnode = left;

		int tx = nx;
		int ty = ny;

		x = nx = xnode.nx;
		y = ny = xnode.ny;

		xnode.x = xnode.nx = tx;
		xnode.y = xnode.ny = ty;

		left = a;
		right = xnode;

		xnode.left = b;
		xnode.right = c;

		//++++++++++++++++++++++++++++++++++
		// begining of the nerr field update
		double xnodedis = new LineSegment((double) x1 / 1000000,
				(double) y1 / 1000000, (double) x2 / 1000000,
				(double) y2 / 1000000).distance(new Coordinate(
				(double) tx / 1000000, (double) ty / 1000000));

		double ldis = 0;
		double rdis = 0;
		if (b != null)
			ldis = b.nerr;

		if (c != null)
			rdis = c.nerr;

		xnodedis += Math.max(ldis, rdis);

		xnode.nerr = (float) xnodedis;
		// end of the nerr field update
		//++++++++++++++++++++++++++++++++++

		int oldrank = nrank;

		nrank = xnode.nrank;
		xnode.nrank = oldrank - xnode.nrank;
	}

	//
	private void lrotate(int x1, int y1, int x2, int y2) {
		// the pre-order traversal is : xaybc
		// the in-order traversal is : axbyc

		LTreeNode a = left;
		LTreeNode b = right.left;
		LTreeNode c = right.right;

		LTreeNode ynode = right;

		int tx = nx;
		int ty = ny;

		x = nx = ynode.nx;
		y = ny = ynode.ny;

		ynode.x = ynode.nx = tx;
		ynode.y = ynode.ny = ty;

		left = ynode;
		right = c;

		ynode.left = a;
		ynode.right = b;

		//++++++++++++++++++++++++++++++++++
		// begining of the nerr field update
		double ynodedis = new LineSegment((double) x1 / 1000000,
				(double) y1 / 1000000, (double) x2 / 1000000,
				(double) y2 / 1000000).distance(new Coordinate(
				(double) tx / 1000000, (double) ty / 1000000));

		double ldis = 0;
		double rdis = 0;
		if (a != null) {
			ldis = a.nerr;
		}

		if (b != null) {
			rdis = b.nerr;
		}

		ynodedis += Math.max(ldis, rdis);

		ynode.nerr = (float) ynodedis;
		// end of the nerr field update
		//++++++++++++++++++++++++++++++++++

		int oldrank = nrank;

		nrank = oldrank + ynode.nrank;
		ynode.nrank = oldrank;

	}
	
	public boolean change (int pos, int x0, int y0, double arc) {
		
		//guard the parameter 
		if (pos < 0 || pos > right.nrank) {
			//beyond the bound of array
			return false;
		}
		
		boolean isRebuildable = change(pos, x0, y0, 0, 0, 0, 0, 0, right.nrank, false, arc);
		if (isRebuildable) {
			int[] diff = new int[1];
			int[] updatediff = new int[1];
			rebuild(pos, 0, 0, 0, 0, 0, right.nrank, 0, right.rank, diff, updatediff);
		}
		
		return isRebuildable;
	}

	//change the coordinate of an existing vertex in the latest dblg-tree
	//inputs:
	//pos : identifier of the vertex which needs changing
	//nx, ny : new coordinate of the target vertex
	//outputs:
	// whether the update incur a rebuilding
		//two endpoints can be changed 
	private boolean change(int pos, int x0, int y0, int x1, int y1, int x2,
			int y2, int si, int se, boolean isCovered, double arc) {

		//distance to the old line segment
		double plDis = new LineSegment(((double) x1) / 1000000,
				((double) y1) / 1000000, ((double) x2) / 1000000,
				((double) y2) / 1000000).distance(new Coordinate(
				((double) x0) / 1000000, ((double) y0) / 1000000));

		boolean retval = false;
		updates++;

		if (!isCovered) {

			if (!isInvalid && plDis <= err) {

			} else {
				if (plDis > err && plDis > nerr) {
					nerr = (float) plDis;
				}
				isInvalid = true;
				isCovered = true;
				if ((double) (se - si - 1) / updates < arc) {
					retval = true;
				}
			}
		} else {
			if (plDis > nerr && plDis > err) {
				nerr = (float) plDis;
			}
		}

		if (si + nrank == pos) {
			nx = x0;
			ny = y0;
			if (!isCovered) {
				isInvalid = true;
				if ((double) (se - si - 1) / updates < arc) {
					retval = true;
				}
			}
		} else if (si + nrank > pos) {
			boolean ret = left.change(pos, x0, y0, x1, y1, x, y, si,
					si + nrank, isCovered, arc);
			return retval || ret;
		} else {
			boolean ret = right.change(pos, x0, y0, x, y, x2, y2, si + nrank,
					se, isCovered, arc);
			return retval || ret;
		}

		return retval;
	}

	public boolean delete(int pos, double arc, Coordinate del) {

		boolean[] isPre = new boolean[1];
		boolean isRebuildable = delete(pos, 0, getSize(), isInvalid, arc,
				isPre, del);

		//right.left.getLatestSize(0, getSize());
		if (isRebuildable) {

			int[] diff = new int[1];
			int[] updatediff = new int[1];
			diff[0] = 0;
			updatediff[0] = 0;
			if (isPre[0]) {
				rebuild(pos - 1, 0, 0, 0, 0, 0, getSize(), 0, right.rank, diff,
						updatediff);
			} else {
				rebuild(pos, 0, 0, 0, 0, 0, getSize(), 0, right.rank, diff,
						updatediff);
			}
		}

		return isRebuildable;
	}

	//delete an existing vertex
	//inputs:
	//
	//outputs:
	// whether the update incur a rebuilding
	private boolean delete(int pos, int si, int se, boolean isCovered,
			double arc, boolean[] isPre, Coordinate del) {

		boolean retval = false;
		updates++;
		if (!isCovered) {
			if (isInvalid) {
				isCovered = true;
				if ((double) (se - si - 1) / updates < arc) {
					retval = true;
				}
			}
		}

		if (si + nrank == pos) {

			del.x = nx;
			del.y = ny;

			if (nrank > 1)
				isPre[0] = true;
			else
				isPre[0] = false;

			cascadeDelete(si, se);

			//getLatestSize(si, se - 1);
			// 
			if (!isCovered)
				isInvalid = true;
		} else if (si + nrank > pos) {
			boolean ret = left.delete(pos, si, si + nrank, isCovered, arc,
					isPre, del);

			if (nrank == 2) {
				isPre[0] = false;
			}
			nrank--;
			return retval || ret;
		} else {
			boolean ret = right.delete(pos, si + nrank, se, isCovered, arc,
					isPre, del);
			if (se - (si + nrank) == 2) {
				isPre[0] = true;
			}
			return retval || ret;
		}

		return retval;
	}

	private void cascadeDelete(int si, int se) {
		if (nrank > 1) {
			LTreeNode ipre = left;
			int nnum = nrank;
			while (nnum - ipre.nrank > 1) {
				nnum -= ipre.nrank;
				ipre = ipre.right;
			}

			nx = ipre.nx;
			ny = ipre.ny;

			ipre.cascadeDelete(si + nrank - ipre.nrank - 1, si + nrank);
			nrank--;

		} else if (se - (si + nrank) > 1) {
			LTreeNode isuc = right;
			int hbound = se;
			while (isuc.nrank > 1) {
				hbound = si + nrank + isuc.nrank;
				isuc = isuc.left;
			}

			nx = isuc.nx;
			ny = isuc.ny;

			isuc.cascadeDelete(si + 1, hbound);

			isuc = right;
			while (isuc.nrank > 1) {
				isuc.nrank--;
				isuc = isuc.left;
			}
			//getLatestSize(si, se - 1);
		}
	}

	private int getLatestSize(int si, int se) {
		int lsize = 0;

		if (nrank > 1) {
			lsize = left.getLatestSize(si, si + nrank);
		}

		int rsize = 0;

		if (se - (si + nrank) > 1) {
			rsize = right.getLatestSize(si + nrank, se);
		}

		//check the consistence of values of nrank
		if (se - si - 1 != lsize + rsize + 1) {
			//throw exception
			//System.out.println("nrank inconsistent here: " + si + "\t" + se);
		}

		return lsize + rsize + 1;
	}

	//an extreme case are not in consideration: when two endpoints need to be updated
	private LTreeNode rebuild(int pos, int x1, int y1, int x2, int y2, int si,
			int se, int ssi, int sse, int[] diff, int[] updatediff) {

		//do a BST like search to find the first invalid subtree and rebuild it.
		if (isInvalid) {

			Coordinate[] coords = new Coordinate[se - si + 1];
			readSubline(coords, 1, si, se);

			//assign the first and last endpoints of the subline
			coords[0] = new Coordinate((double) x1 / 1000000,
					(double) y1 / 1000000);
			coords[se - si] = new Coordinate((double) x2 / 1000000,
					(double) y2 / 1000000);

			//the difference of the size of the stable subtree and that of the latest tree
			int ospan = sse - ssi - 1;
			int nspan = se - si - 1;

			//what if the difference between the 
			diff[0] = nspan - ospan;

			updatediff[0] = updates;

			LTreeNode nnd = LTreeNode.simplify(coords, si - si, se - si);
			return nnd;

		} else if (si + nrank > pos) {
			left = left.rebuild(pos, x1, y1, x, y, si, si + nrank, ssi, ssi
					+ rank, diff, updatediff);
			//update the rank of stable tree.
			rank += diff[0];
			updates -= updatediff[0];
		} else if (si + nrank < pos) {
			right = right.rebuild(pos, x, y, x2, y2, si + nrank, se,
					ssi + rank, sse, diff, updatediff);
			updates -= updatediff[0];
		} else {
			//here means 
			// there is only one case for this
			if (nrank == 1 && left != null) {
				left = null;
			} else if (se - (si + nrank) == 1 && right != null) {
				right = null;
			} else {
				//throw exception
				//System.out.println("There is something wrong with leaf deletion ");
			}

			rank = nrank;
			x = nx;
			y = ny;
			err = nerr;

			updatediff[0] = 1;
			diff[0] = -1;

			// throw exception about can't find the root of the invalid subtree
		}
		return this;
	}

	public int getSubSize() {
		int lsize = 0;
		int rsize = 0;
		if (left != null) {
			lsize = left.getSubSize();
		}

		if (right != null) {
			rsize = right.getSubSize();
		}

		return lsize + rsize + 1;
	}

	public int toArray(Coordinate[] coords, int cursor, boolean isLatest) {
		int ocursor = cursor;
		if (left != null) {
			cursor += left.toArray(coords, cursor, isLatest);
		}

		if (isLatest) {
			coords[cursor] = new Coordinate((double) nx / 1000000,
					(double) ny / 1000000);
		} else {
			coords[cursor] = new Coordinate((double) x / 1000000,
					(double) y / 1000000);
		}
		cursor++;

		if (right != null) {
			cursor += right.toArray(coords, cursor, isLatest);
		}

		return cursor - ocursor;
	}

	//test the consistency of the tree
	public void test() {
		right.left.getLatestSize(0, right.nrank);
	}

	private void cutOff() {
		if (left != null) {
			if (left.rank < 0) {
				left = null;
			} else {
				left.cutOff();
			}
		}

		if (right != null) {
			if (right.rank < 0) {
				right = null;
			} else {
				right.cutOff();
			}
		}
	}

	private LTreeNode fetchAll(int si, int se) {
		LTreeNode nd = duplicate();

		if (nrank > 1) {
			nd.left = left.fetchAll(si, si + nrank);
		}

		if (se - (si + nrank) > 1) {
			nd.right = right.fetchAll(si + nrank, se);
		}

		return nd;
	}

	private static LTreeNode simplify(Coordinate[] coords, int i, int j) {
		if (i + 1 == j)
			return null;

		double maxDis = -1;
		int maxPos = i + 1;

		LineSegment seg = new LineSegment(coords[i], coords[j]);

		for (int k = i + 1; k < j; k++) {
			double dis = seg.distance(coords[k]);

			if (maxDis < dis) {
				maxDis = dis;
				maxPos = k;
			}
		}

		//construct a node 
		LTreeNode nd = new LTreeNode();
		nd.setValues(maxPos - i, maxPos - i, (float) maxDis, (float) maxDis,
				(int) (coords[maxPos].x * 1000000),
				(int) (coords[maxPos].y * 1000000),
				(int) (coords[maxPos].x * 1000000),
				(int) (coords[maxPos].y * 1000000));

		nd.left = simplify(coords, i, maxPos);
		nd.right = simplify(coords, maxPos, j);
		return nd;
	}

	private LTreeNode duplicate() {
		LTreeNode nd = new LTreeNode();
		nd.rank = rank;
		nd.err = err;
		nd.x = x;
		nd.y = y;

		nd.nrank = nrank;
		nd.nerr = nerr;
		nd.nx = nx;
		nd.ny = ny;

		nd.updates = updates;

		return nd;
	}

	private int readSubline(Coordinate[] coords, int cursor, int si, int se) {
		int ocursor = cursor;
		//read left subtree
		if (nrank > 1) {
			cursor += left.readSubline(coords, cursor, si, si + nrank);
		}

		coords[cursor] = new Coordinate((double) nx / 1000000,
				(double) ny / 1000000);
		cursor++;

		//read right subtree
		if (se - (si + nrank) > 1) {
			cursor += right.readSubline(coords, cursor, si + nrank, se);
		}
		return cursor - ocursor;
	}

	class FullnodeComp implements Comparator<Fullnode> {

		public int compare(Fullnode o1, Fullnode o2) {
			if (o1.node.err > o2.node.err) {
				return -1;
			} else if (o1.node.err < o2.node.err) {
				return 1;
			}

			return 0;
		}
	}

	//a standalone node
	class Fullnode {
		int si;
		int se;
		int x1;
		int y1;
		int x2;
		int y2;
		LTreeNode node;

		public void setEndpoints(int x1, int y1, int x2, int y2) {
			this.x1 = x1;
			this.y1 = y1;
			this.x2 = x2;
			this.y2 = y2;
		}
	}
}
